The problem can be found at the following link: Question Link
This question is another apllication of BST property of inordere traversal. So for solving this,
- I use in-order traversals of both trees to obtain sorted arrays
t1
andt2
. - Then, I iterate through these arrays with two pointers, comparing the sum of elements at the pointers with the target
x
. Based on the comparison, I adjust the pointers to find pairs that sum tox
.
- Time Complexity:
O(N + M)
, whereN
andM
are the numbers of nodes in the two trees. - Auxiliary Space Complexity:
O(N + M)
, as we store in-order traversals in arrays.
class Solution {
public:
void inorder(Node* root, vector<int>& v) {
if (root == NULL)
return;
inorder(root->left, v);
v.push_back(root->data);
inorder(root->right, v);
}
int countPairs(Node* root1, Node* root2, int x) {
vector<int> t1, t2;
inorder(root1, t1);
inorder(root2, t2);
int i = 0, j = t2.size() - 1;
int out = 0;
while (i < t1.size() && j >= 0) {
int sum = t1[i] + t2[j];
if (sum > x)
--j;
else if (sum < x)
++i;
else {
++out;
++i;
--j;
}
}
return out;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.